With increasing loads on mobile radio communication systems, the efficient utilization of the limited radio bandwidth becomes increasingly important. Frequency reuse over spatially separated areas has become a common technique used to increase system capacity. Fixed Channel Allocation (FCA) systems, where each cell is statically assigned a fixed set of frequencies (or channels) that are non-interfering with neighboring sets, do not often utilize the available capacity. This is particularly true when the load across cells is uneven. Dynamic Channel Allocation (DCA) strategies, on the other hand, are more flexible and allow every cell to use any of the global pool of channels, subject to the current state of the changing interference constraints.
In Dynamic Channel Allocation systems that provide increased capacity over FCA, the system has to decide (1) what channel to allocate to a new call, and (2) what reconfigurations are to be performed to the current channel allocations whenever a call completes or whenever the mobiles move. The former is referred to as call admission and the latter as reconfiguration.
Several different algorithms for dynamic channel allocation have been proposed in the literature. At one extreme are the optimal packing schemes that, for each given configuration, determine the best possible way of accommodating all the ongoing calls using as few channels as possible. Such algorithms achieve optimum capacity by definition, but do so at the cost of a complexity and expense that prohibits practical implementation. Furthermore, the channel allocation for each configuration of the mobiles is computed anew as the configurations change with time. Each new optimal allocation is likely to bear little resemblance to the prior allocation. This may result in a large number of calls being reassigned to different channels. The cost of constantly reassigning in a real system may be considerable. Also, there may be no feasible way for the system to "migrate" from one allocation to the next short of requiring all calls to switch to a new channel in a synchronized fashion.
The problems with optimal packing schemes have motivated a number of simplistic dynamic channel allocation systems. The simplest of these handles a call admission by having the new call acquire a channel that is not being used in "its vicinity", if such a channel exists. Otherwise, the call is blocked. A somewhat more aggressive algorithm also allows a new call to acquire a channel by displacing a nearby interferer, but only if the displaced call is able to acquire another channel not used in its vicinity to thereby restrict the ripple effect of channel reassignments. Most of these systems deal only with call admissions, and do not consider channel reassignments at call terminations or due to mobility. Channel reassignments required due to a handoff from one cell to another are treated as a call termination in one cell and as a new call in another. Some variants of the scheme specify an ordering of the channels to be tried in sequence. Such ordered schemes perform channel reassignments at call terminations by requiring that the active calls in a cell use the topmost available channels according to the channel ordering for the cell. The attractive simplicity of such schemes comes from enforcing hard constraints on the number of possible reassignments. Even when a few extra reassignments may result in a much improved allocation, the algorithms may forbid such a reassignment. Furthermore, the possibility of exploiting potentially improved reassignments when calls terminate or mobiles move are not explored by these algorithms.